//堆排序
//大顶堆
function heapify(arr, heapSize, rootIndex) {
    let largest= rootIndex;
    const left=2*rootIndex+1;
    const right=2*rootIndex+2;

    //比较左子树与根节点
    if(left<heapSize&&arr[left]>arr[largest]){
        largest=left;
    }
    //比较右子树与根节点
    if(right<heapSize&&arr[right]>arr[largest]){
        largest=right;
    }
    //如果根节点不是最大值，则交换根节点与最大值
    if(largest!==rootIndex){
        [arr[rootIndex],arr[largest]]=[arr[largest],arr[rootIndex]];
        //递归地对交换后的子树进行堆化
        heapify(arr,heapSize,largest);
    }
}
function heapSort(arr){
    const n=arr.length;
    //构建最大堆
    for(let i=Math.floor(n/2)-1;i>=0;i--){
        heapify(arr,n,i);
    }
    //从堆顶开始取出元素，放到数组末尾，然后重新堆化
    for(let i=n-1;i>=0;i--){
        [arr[0],arr[i]]=[arr[i],arr[0]];    //交换堆顶和堆底元素
        heapify(arr,i,0);                  //重新堆化
    }
    return arr;
}


//小顶堆
function heapifyMin(arr, heapSize, rootIndex) {
    let smallest = rootIndex;
    const left = 2 * rootIndex + 1;
    const right = 2 * rootIndex + 2;
    // 比较左子树与根节点
    if (left < heapSize && arr[left] < arr[smallest]) {
        smallest = left;
    }
    // 比较右子树与根节点
    if (right < heapSize && arr[right] < arr[smallest]) {
        smallest = right;
    }
    // 如果根节点不是最小值，则交换根节点与最小值
    if (smallest !== rootIndex) {
        [arr[rootIndex], arr[smallest]] = [arr[smallest], arr[rootIndex]];
        // 递归地对交换后的子树进行堆化
        heapifyMin(arr, heapSize, smallest);
    }
}
function heapSortMin(arr) {
    const n = arr.length;
    // 构建最小堆
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapifyMin(arr, n, i);
    }
    // 从堆顶开始取出元素，放到数组末尾，然后重新堆化
    for (let i = n - 1; i >= 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];    // 交换堆顶和堆底元素
        heapifyMin(arr, i, 0);                  // 重新堆化
    }
    return arr;
}
console.log(heapSortMin([5, 2, 1, 9, 6]));